1. Field of the Invention.
The present invention relates to a data communication system employing improved packet switching techniques for extending the communication coverage between local networks in an efficient, responsive and reliable manner over a wide geographical area.
2. Description of the Prior Art.
Store-and-forward switching has existed for years in telegraphy, where it is commonly called message switching. Message switching is intended primarily for non-real-time traffic of messages between people. Typically, a telegraphic message switching system employs a star-structured network having a centrally dominating storage facility at the center. The messages are usually filed for retrieval at some future time for delivery in a fraction of an hour over large distances.
In the field of data communications, a type of store-and-forward switching system has been used which is called packet switching. Packet switching is intended primarily for real-time, machine-to-machine traffic, including that between terminals and computers. Packet switching systems such as Arpanet and Telenet are in wide use in this country and are well known to those skilled in this art.
In general, transmission of data in a packet switching system achieves delivery of each packet or message in a fraction of a second and is essential for machine-to-machine interactive communication. Packet systems are usually of a mesh structure of interconnected switching nodes with no particular dominating location and individual packets are deleted from each transmitting node memory as soon as they are correctly received at the next node. Each packet is made up of a group of binary digits which includes a header portion of source and destination address data, call control signals and possibly error-control information in a specified format and a data portion. In such systems, messages are directly sent from a terminal or host computer to a corresponding packet switching-node processor. The messages are formatted at the switching-node processor into one or more packets and are then transmitted to another switching-node via a transmission channel until they reach their destination. Each switching-node that receives the packet stores the packet, examines the destination address on each packet and selects the next switching node for transmission on the route. Sometimes the most direct route is not selected because of equipment malfunctions or message traffic congestion on a particular route. In such cases, another route will be selected by the switching node. Each switching-node processor is conventionally designed to make selections and routing decisions for expeditious transfer of the packet.
In conventional packet switching systems, long messages are chopped into slices (packets) of a nominal 128, eight-bit bytes. Since packets are relatively small, they can be queued in the memory of the respective switching node processors and passed rapidly from node to node. At the destination node, the original message is reassembled from the packets received by the destination switching node processor and passed to its corresponding terminal or host computer.
There is, of course, some delay in transmitting complete messages in a packet switching system and these delays are caused not only by the length of the packets that are relayed through the system but also by the propagation and queuing delays contributed by the number of intermediate nodes or hops that may be required to switch packets between the source and the destination.
Recently, several new techniques for short-distance, high-speed data communications systems, have been introduced, which are termed local networks. A local network is a system designed to interconnect computers and terminals over a restricted geographical area, typically less than 2 kilometers in distance. A number of implementations exist which range from star, ring, and bus structure topologies. Devices which connect to the local network must adhere to some standard set of interface procedures. Data transmitted from a source device flows through the network as destination addressed packets without being stored for any length of time within the network itself. Local networks are generally characterized with low packet transmission delays, low error rates, and usually employ both broadcast and multi-address communication features.
Local networks usually share a common transmission facility or medium; and some type of contention access is used as a means for multiplexing or sharing this common medium resource. In a contention system, devices are free to transmit over the network medium whenever they have data to send. The devices are designed to eliminate the occurrence of multiple devices simultaneously sending packets over the common medium, since simultaneously or overlapping transmissions would destroy the transmitted packets in whole or in part. In such systems, conflict resolving techniques are used, such as described in commonly assigned U.S. Pat. No. 4,234,952, which is incorporated herein by reference.
Local networks utilizing contention access can be quite efficient and reliable since they eliminate the need for any complicated control information to flow between network stations. Contention networks, however, have certain limitations in the area of network distance, packet size and data rates, since the propagation delay of the medium determines the vulnerable time in which contention may occur. As such, contention networks are normally restricted to a local area of approximately 2 kilometers.
Interconnection of local networks has been achieved by using packet gateways and appropriate software addressing techniques. Gateways are used for coupling point-to-point systems, whereby each gateway repeats those packets addressed to itself as an intermediary. Since gateways have both packet buffers as well as addresses, a number of gateways may be used to interconnect each local network. Hence, a failure of the gateway need not partition a local network from interconnection of other networks. A more complete description of that technique is given in the article entitled "A Protocol for Packet Network Communication", published in Vol. Com-22, No. 5, May, 1974 of IEEE Transactions on Communications and is incorporated herein by reference.
The gateway technique is similar to the store-and-forward packet switching techniques in that queue delays, as well as switching delays, for routing are incurred for each of the intermediate gateways. Hence, the system performance degrades to a typical store-and-forward packet switching network.